﻿using System;

namespace SortAndDatastruct {
    /// <summary>
    /// 线性选择顺序统计量，效率O(n).
    /// </summary>
    class LinearizeSelect {
        /// <summary>
        /// 最坏情况下线性选择的外部接口
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Index">顺序统计量的Index</param>
        /// <returns>选择结果</returns>
        internal int WorstConditionLinear(ref int[] Array, int Index) {
            if (Index < 0 || Index > Array.Length) return -1;
            return WorstConditionSelect(ref Array, 0, Array.Length - 1, Index);
        }
        /// <summary>
        /// 期望线性选择的外部接口
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Index">顺序统计量的Index</param>
        /// <returns>选择结果</returns>
        internal int ExpectLinear(ref int[] Array, int Index) {
            if (Index < 0 || Index > Array.Length) return -1;
            return ExpectLinearSelect(ref Array, 0, Array.Length - 1, Index);
        }
        /// <summary>
        /// 最坏情况下线性的选择第index个顺序统计量
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <param name="Index">顺序统计量的index</param>
        /// <returns>选择结果</returns>
        int WorstConditionSelect(ref int[] Array, int Left, int Right, int Index) {
            if (Left == Right) return Array[Left];
            int Mid = MedianPartition(ref Array, Left, Right);
            int StateNum = Mid + 1;
            if (StateNum == Index) {
                return Array[Mid];
            } else if (StateNum > Index) {
                return WorstConditionSelect(ref Array, Left, Mid - 1, Index);
            } else {
                return WorstConditionSelect(ref Array, Mid + 1, Right, Index);
            }
        }
        /// <summary>
        /// 期望线性选择，最坏情况是O(n*n)，但期望值是O(n)
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <param name="Index">顺序统计量的index</param>
        /// <returns>选择结果</returns>
        int ExpectLinearSelect(ref int[] Array, int Left, int Right, int Index) {
            if (Left == Right) return Array[Left];
            int Mid = RandomPartition(ref Array, Left, Right);
            int StateNum = Mid + 1;
            if (StateNum == Index) {
                return Array[Mid];
            } else if (StateNum > Index) {
                return ExpectLinearSelect(ref Array, Left, Mid - 1, Index);
            } else {
                return ExpectLinearSelect(ref Array, Mid + 1, Right, Index);
            }
        }
        /// <summary>
        /// 将数组划分成2个部分，一部分比基准小，一部分比基准大
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <returns>基准的Index</returns>
        int Partition(ref int[] Array, int Left, int Right) {
            int x = Array[Right];
            int index = Left - 1;
            for (int i = Left; i < Right; ++i) {
                if (Array[i] <= x) {
                    SortHelper.SWAP(ref Array[++index], ref Array[i]);
                }
            }
            SortHelper.SWAP(ref Array[++index], ref Array[Right]);
            return index;
        }
        /// <summary>
        /// 从数据源中随机的找个基准进行划分
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <returns>基准的Index</returns>
        int RandomPartition(ref int[] Array, int Left, int Right) {
            Random ran = new Random();
            SortHelper.SWAP(ref Array[ran.Next(Left, Right)], ref Array[Right]);
            return Partition(ref Array, Left, Right);
        }
        /// <summary>
        /// 从数据源中找出中位数进行划分
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <returns>基准的Index</returns>
        int MedianPartition(ref int[] Array, int Left, int Right) {
            int mid = GetMM(ref Array, Left, Right);
            int index = Left - 1;
            int MidIndex = 0;
            for (int i = Left; i <= Right; ++i) {
                if (Array[i] < mid) {
                    SortHelper.SWAP(ref Array[++index], ref Array[i]);
                }
                if (Array[i] == mid) {
                    MidIndex = i;
                }
            }
            SortHelper.SWAP(ref Array[++index], ref Array[MidIndex]);
            return index;
        }
        /// <summary>
        /// 获取5分子数组的中位数
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Length">数据源的有效长度</param>
        /// <returns>中位数</returns>
        int GetMedian(ref int[] Array, int Length) {
            if (Array == null || Length < 1) throw new ArgumentException();
            if (Array.Length == 1) return Array[0];
            for (int i = 1; i < Length; ++i) {
                int key = Array[i];
                int j = i - 1;
                while (j >= 0 && key < Array[j]) {
                    Array[j + 1] = Array[j--];
                }
                Array[j + 1] = key;
            }
            if (Length % 2 == 0) return Array[Length / 2 - 1];
            return Array[Length / 2];
        }
        /// <summary>
        /// 获取数据源划分成若干个长度为5的子数组
        /// 先找出子数组的中位数，然后找出中位数的中位数
        /// </summary>
        /// <param name="Array">数据源</param>
        /// <param name="Left">数据源的左边</param>
        /// <param name="Right">数据源的右边</param>
        /// <returns>中位数的中位数</returns>
        int GetMM(ref int[] Array, int Left, int Right) {
            int Len = Right - Left + 1;
            int MidCnt = (int)Math.Ceiling(Len / 5.0);
            int[] MidArr = new int[MidCnt];
            int[][] SubArrs = new int[MidCnt][];
            int i = 0, offset = 0;
            for (; i < MidCnt - 1; ++i, offset += 5) {
                SubArrs[i] = new int[5];
                for (int j = 0; j < 5; ++j) {//从原数组构造子数组
                    int index = j + offset + Left;
                    SubArrs[i][j] = Array[index];
                }
                MidArr[i] = GetMedian(ref SubArrs[i], SubArrs[i].Length);
            }
            int cnt = 0;
            SubArrs[i] = new int[5];
            for (int j = 0; j < 5; ++j) {
                int index = j + offset + Left;
                if (index < Array.Length) {
                    SubArrs[i][j] = Array[index];
                    ++cnt;
                }
            }
            MidArr[i] = GetMedian(ref SubArrs[i], cnt);
            //递归调用找出其中位数的中位数
            if (MidArr.Length % 2 == 0) return WorstConditionLinear(ref MidArr, MidArr.Length / 2 - 1);
            return WorstConditionLinear(ref MidArr, MidArr.Length / 2);
        }
    }
}
